#include <cmath>
#include <sstream>
#include <pthread.h>
#include <sys/time.h>
#include <string.h>
#include <map>
#include "shorthand.h"
#include "math.h"

#ifndef _UTIL_H_
#define _UTIL_H_

#define DEBUG(var) cout << #var << " = " << var << endl;
#define BIND_HASH(var) const uint64 var = Fingerprint(#var);
#define DEBUG_RETURN(x) { CHECK(x); return (x); }

struct Config;
extern Config * G_CONFIG;
extern pthread_mutex_t G_LOCK, G_PRINT_LOCK;
extern bool GDebug;
extern const uint64 G_PAGE_SIZE; // In bytes

// grab len bits from n starting at bit start.
// bit 0 is least significant bit
inline uint64 GetBits (uint64 n, uint64 start, uint64 len) {
  return (n >> start) & ( (1ull << len) - 1);
}

// set len bits in *dest.
// the bits to be written are at the low end of source.
// the high bits of source are ignored.
inline void SetBits
(uint64 *dest, uint64 source, uint64 start, uint64 len) {
  uint64 mask = (1ull << len) - 1;
  uint64 flips = (((*dest >> start) ^ source) & mask ) << start; 
  *dest ^= flips;
}

void InitUtil(int argc, char **argv);

void CheckObjectSizes();
void CheckLittleEndian();

inline void IncrementReport(int64 *statistic, int64 epoch, const char* o) {
  int64 val = __sync_fetch_and_add(statistic, 1);
  if (!(val % epoch)) cout << o << " " << val << endl;
}

struct Config {
  void Load(string fn);
  void LoadCommandLineParams(int argc, char **argv);

  string GetString(string key);
  int64 GetInt(string key);
  bool Exists(string key);
  map<string, string> map_;
};

inline string ConfigString(string key) { return G_CONFIG->GetString(key); }
inline int64 ConfigInt(string key) { 
  return atoll(ConfigString(key).c_str()); }
inline double ConfigDouble(string key) { 
  return atof(ConfigString(key).c_str()); }

#define COMPARE_BY(a,b,x) \
  if (a.x < b.x) return true; if (b.x < a.x) return false;

struct PrintLock {
  PrintLock() { pthread_mutex_lock(&G_PRINT_LOCK); }
  ~PrintLock() { pthread_mutex_unlock(&G_PRINT_LOCK); }
  template <class T>
  const PrintLock & operator <<  (const T & t) const {cout << t; return *this;}
};
#define COUT PrintLock()

// Some constants we need
extern float OneOverRandMax;

inline uint64 Shuffle(uint64 x) { return (x >> 32) | (x  << 32); }

inline uint64 Fingerprint(uint64 x, uint64 y = 1) {
  return Shuffle(x * 0x1852389021532685ull + y * 0x4251256931465823ull); }

inline uint64 Fingerprint(uint64 x, uint64 y, uint64 z) {
  return Fingerprint(Fingerprint(x, y), z); }

inline uint64 FingerprintCharArray(const char * s, 
				   uint64 size, uint64 level = 0) {
  uint64 ret = Fingerprint(size, level);
  uint64 pos = 0;
  uint64 x;
  for (; pos+8 <= size; pos += 8) {
    memcpy(&x, &s[pos], 8);
    ret = Fingerprint(ret, x);    
  }
  x = 0;
  memcpy(&x, &s[pos], size - pos);
  ret = Fingerprint(ret, x);
  return ret;
}
inline uint64 Fingerprint(const string & s, uint64 level = 0) {
  return FingerprintCharArray((const char *)s.c_str(), s.size(), level);
}

inline uint64 Fingerprint(const char * s, uint64 level = 0) {
  return FingerprintCharArray(s, strlen((const char *)s), level);
}

template<class T>
struct PointerHash {
  size_t operator () (const T * p) const {
    return (size_t)(p);
  }
};
template <class T> 
struct SimpleHash {
  size_t operator () (const T & p) const { return (size_t) p;}
};
struct StringHash {
  size_t operator () (const string & s) const { return (size_t) Fingerprint(s); }
};

/*
// pthreads
inline void Lock(pthread_mutex_t& m, const char* name = NULL) {
  //if (name) cout << "trying to lock " << name << endl;
  pthread_mutex_lock(&m);
  //if (name) cout << "locked " << name << endl;
}

inline void Unlock(pthread_mutex_t& m, const char* name = NULL) {
  //if (name) cout << "unlocking " << name << endl;
  pthread_mutex_unlock(&m);
}
*/

// Lets you create a lock that gets garbaged via object destruction
// Takes a lock_now parameter to accomodate locks that sometimes happen
struct MutexLocker {
MutexLocker(pthread_mutex_t * lock, bool lock_now = true) :lock_(lock), locked_(false), crash_on_destructor_(false) {
  if (lock_now) Lock();
}
  void Lock() { pthread_mutex_lock(lock_); locked_ = true;}
  void Unlock() { pthread_mutex_unlock(lock_); locked_ = false;}
  // returns true on success. 
  bool TryLock() { 
    if (pthread_mutex_trylock(lock_) == 0) locked_ = true;
    return locked_;
  }
  bool IsLocked() { return locked_;}
  ~MutexLocker() { 
    if (IsLocked()) {
      CHECK(!crash_on_destructor_);
      Unlock(); } }
  pthread_mutex_t *lock_;
  bool locked_;
  bool crash_on_destructor_;
};

// Lets you create a lock that gets garbaged via object destruction
// Takes a lock_now parameter to accomodate locks that sometimes happen
struct RWLocker {
  enum State {
    UNLOCKED,
    READ_LOCK, 
    WRITE_LOCK,
  };
RWLocker(pthread_rwlock_t * lock, bool crash_on_destructor = true) :lock_(lock), state_(UNLOCKED), crash_on_destructor_(crash_on_destructor) {}
  
  void RLock() { 
    CHECK(state_ == UNLOCKED);
    pthread_rwlock_rdlock(lock_);
    state_ = READ_LOCK; }
  void WLock() { 
    CHECK(state_ != WRITE_LOCK);
    pthread_rwlock_wrlock(lock_);
    state_ = WRITE_LOCK; }
  void Unlock() { 
    CHECK(state_ != UNLOCKED);
    pthread_rwlock_unlock(lock_); 
    state_ = UNLOCKED; 
  }
  ~RWLocker() { 
    if (state_ != UNLOCKED) {
      CHECK(!crash_on_destructor_);
      Unlock(); } }
  pthread_rwlock_t *lock_;
  State state_;
  bool crash_on_destructor_;
};


// A way to synchronize threads at a barrier
// First call Init, then call Pass, it will let everyone past the Pass
// once everyone has called it
struct Barrier {
  void Init(uint64 num_threads) {
    num_threads_ = num_threads;
    num_finished_ = 0;
    pthread_mutex_init(&lock_, NULL);
    pthread_cond_init(&finished_cv_, NULL);
  }
  void Pass() {
    pthread_mutex_lock(&lock_);
    num_finished_++;
    if (num_finished_ == num_threads_) {
      pthread_cond_broadcast(&finished_cv_);
      num_finished_ = 0;
    } else {
      pthread_cond_wait(&finished_cv_, &lock_);
    }
    pthread_mutex_unlock(&lock_);
  }
  pthread_cond_t finished_cv_;
  pthread_mutex_t lock_;
  uint64 num_threads_;
  uint64 num_finished_;
};


struct RNG {
  RNG() { x_ = rand();}
  void Seed(uint64 seed) {x_ = seed;}
  uint64 Random() {
    x_ = x_ * 6364136223846793005ull + 1442695040888963407ull;
    return ( (x_ & 0xffffffff00000000ull) >> 32) 
      | ( (x_ & 0x00000000ffffffffull) << 32);
  }
  uint64 Round(double x) {
    CHECK(x >= 0.0);
    uint64 start = (uint64) x;
    double remainder = x - start;
    if (RandomFraction() < remainder) start++;
    return start;
  }

  uint64 x_;

  double RandomFraction();
  uint64 RandomImportance(uint64 external);
  uint64 Gamble(uint64 bet, uint64 payout) {
    if (bet >= payout) return bet;
    if ((Random() % payout) < bet) return payout;
    return 0;
  }
};

// Some randomness
// returns a random float between 0 and 1 inclusive
uint64 BitCount(uint64 x);

// vector of pairs of (i, v[i]) sorted by decreasing v[i]
vector<pair<int, float> > DecreasingSortWithIndices(const vector<float>& v);

// Work on strings
string Upcase(const string& s);

template <class A, class B>
struct GreaterSecond {
  bool operator () (const pair<A, B> &p1, const pair<A, B> &p2) {
    return (p1.second > p2.second);
  }
};
template <class A, class B>
struct LessFirst {
  bool operator () (const pair<A, B> &p1, const pair<A, B> &p2) {
    return (p1.first < p2.first);
  }
};

template <class A>
string VectorToString(const vector<A> & v) {
  ostringstream out;
  out << "(";
  for (uint32 i=0; i<v.size(); i++) { 
    if (i>0) out << " ";
    out << v[i];
  }
  out << ")";
  return out.str();
}

struct StableVectorException {
  StableVectorException(void *v) :vector_(v) {}
  StableVectorException(const StableVectorException & o) :vector_(o.vector_){}
  void *vector_;
};

// a fixed capacity vector that does not move in memory
template<class A> struct StableVector {
  StableVector(uint64 capacity) {
    capacity_ = capacity;
    current_ = data_ = new A[capacity_];
    limit_ = data_ + capacity_;
    descriptor_ = "unknown";
  }
  ~StableVector() {
    delete [] data_;
  }
  uint64 size() {  return current_ - data_; }
  A & operator [](int i) { return data_[i];}
  const A & operator [] (int i) const { return data_[i];}
  void extend() { current_++;}
  void push_back() {
    if (current_ >= limit_) {
      cout << "Stable vector exception on " << descriptor_ << endl;
      throw StableVectorException((void *)this);
    }
    current_++;
  }
  void push_back(const A & a) { 
    if (current_ >= limit_) {
      cout << "Stable vector exception on " << descriptor_ << endl;
      throw StableVectorException((void *)this);
    }
    *current_ = a;
    current_++;
  }
  void pop_back() {current_--;}
  void clear() {current_ = data_;}
  void resize(uint64 new_size) { current_ = data_ + new_size; }
  void RelativeResize(int64 delta) { current_ += delta;}
  A & back() { return current_[-1]; }
  A * begin() { return data_;}
  A * end() { return current_;}
  bool NearCapacity(uint64 margin) { return (current_ + margin >= limit_); }

  A *current_;
  A *data_;
  A *limit_;
  uint64 capacity_;
  const char * descriptor_;
};

inline string UpperCase(const string & s) {
  string sc = s;
  for (uint64 i=0; i<sc.size(); i++) sc[i] = toupper(sc[i]); 
  return sc; }

// increments an int on construction and decrements it on destruction
struct Increment { 
  Increment(int *target) :target_(target) {(*target_)++;}
  ~Increment() {(*target_)--;}
  int * target_;
};

int UltimateDestination(const map<int, int> & m, int source);

inline int64 TimeNS() {
  struct timeval tm;
  gettimeofday(&tm, NULL);
  return (uint64)tm.tv_sec * 1000000000ull + tm.tv_usec * 1000;
}

/*
inline int64 ThreadTimeNS() {
  timespec ts;
  clock_gettime(CLOCK_REALTIME, &ts);
  return int64(ts.tv_sec) * 1000000000ull + (int64)ts.tv_nsec;
}
*/


// Putting a string back on an istream
void putback(istream & in, string s);

string ReadLine(istream & in);

// Reading a file or a stream into memory?
void ReadIntoString(string * res, istream & in);
void ReadFileIntoString(string * res, string filename);

bool FileExists(string fn);
void DeleteFile(string fn);

// MMapping a file
// Returns results in the passed in parameters
bool Mmap (string filename, char ** block, uint64 * length);

struct Memblock {
  Memblock() :size_(0), data_(NULL) {}
  // Memblock(char *d, uint64 s) 
  // : size_(s), data_(d) {}
  Memblock(const char* d, uint64 s) 
  : size_(s), data_((char*) d) {}
  uint64 size_;
  char * data_;
  bool Fail() { return !data_;}
  char * end() { return data_ + size_;}
  char * begin() { return data_; }
  void SetBegin(char *p) { CHECK(p <= end()); size_ = end() - p; data_ = p; }
  void SetEnd(char *p) { CHECK(begin() <= p); size_ = p - begin(); }
  uint64 size() { return size_; }
  bool IsZeroes() {
    for (uint64 i=0; i<size_; i++) if (data_[i] != 0) return false;
    return true;
  }
  bool IsProbablyZeroes(int n) {
    RNG r;
    for (uint64 i=0; i<(uint64)n; i++)
      if (data_[r.Random() % size_] != 0) return false;
    return true;
  }
  void WriteToFile(string fn);
  void ReadFromFile(string fn);
};

Memblock ExpandToEncodedNumber(Memblock m);

inline uint64 Fingerprint(Memblock m) { 
  return FingerprintCharArray(m.begin(), m.size_);}

inline Memblock Mmap2(string filename) {
  Memblock ret;
  if (!Mmap(filename, &ret.data_, &ret.size_)) {
    ret.data_ = NULL;
    cout << "mmap failed on file " << filename << endl;
  }
  return ret; 
}

inline uint64 Touch(Memblock b) {
  uint64 sum = 0;
  for (char *p = b.begin(); p<b.end(); p+=64) sum += *p;
  cout << "Touched " << b.size_ << " bytes sum=" << sum << endl;
  return sum;
}

// pad data to word-align, then write, prefixed by an 8-byte size
void WriteSizePrefixed(ostream *output, const char *data, uint64 size);

template <class T> void Read(const char **p, T * dest) {
  memcpy(dest, *p, sizeof(T));
  *p += sizeof(T);  
}

template <class T> void Write(ostream * output, const T & data) {
  output->write((const char *)&data, sizeof(T));
}

inline const char * ReadSizePrefixed(const char ** p) {
  uint64 size;
  Read(p, &size);
  const char * ret = *p;
  *p += size;
  return ret;
}

inline int HexToInt(const string &h) {
  istringstream in(h);
  int ret;
  in >> hex >> ret;
  return ret;
}

// For reading and writing raw binary data using strings as
// intermediate representations.

template <class T> T ReadType(const char ** source) {
  T ret;
  memcpy(&ret, *source, sizeof(T));
  *source += sizeof(T);
  return ret;
} 

template<class T> string RawString(const T & t) {
  return string((const char *)&t, sizeof(T));
}

string itoa(int64 i);

// Predicate takes an int64.
// It is assumed that predicate returns false for all values less than an unknown
//  x and true for all values greater than or equal to x. 
//  It is assumed that low <= x <= high
//  Returns x.
template <class Predicate> 
int64 FirstSatisfaction(int64 low, int64 high, Predicate & predicate) {
  if (low == high) return low;
  int64 mid = low + (high - low) / 2;
  bool result = predicate(mid);
  if (result) return FirstSatisfaction(low, mid, predicate);
  return FirstSatisfaction(mid+1, high, predicate);
}

// compute k^n
uint64 UInt64Pow(uint64 k, uint64 n);

// a stack where the bottom falls out automatically when the stack grows too big
template<class T> struct BottomlessStack {
  BottomlessStack(uint64 size) {
    size_ = size;
    data_ = new T[size_];
    clear();
  }
  ~BottomlessStack() {
    delete [] data_;
  }
  void clear() {
    bottom_ = top_ = 0;
    bottom_lost_ = false;
  }
  uint64 depth() {
    return (top_ + size_ - bottom_) % size_;
  }
  void push(const T & t) {
    if (depth() + 1 == size_) {
      bottom_ = (bottom_ + 1) % size_;
      bottom_lost_ = true;
    }
    data_[top_] = t;
    top_ = (top_ + 1) % size_;
  }
  void pop() {
    CHECK(depth() > 0);
    top_ = (top_ + size_ - 1) % size_;
  }
  T & top() {
    return data_[(top_ + size_ - 1) % size_];
  }

  T * data_;
  uint64 bottom_;
  uint64 top_;
  uint64 size_;
  bool bottom_lost_;
};

inline uint64 ShardBegin(uint64 total, uint64 num_shards, uint64 shard_num) {
  return shard_num * total / num_shards;
}

inline uint64 ShardEnd(uint64 total, uint64 num_shards, uint64 shard_num) {
  return (1 + shard_num) * total / num_shards;
}

inline pair<uint64, uint64> Shard(uint64 total, 
				  uint64 num_shards, uint64 shard_num) {
  return make_pair(ShardBegin(total, num_shards, shard_num),
		   ShardEnd(total, num_shards, shard_num));
}


inline uint64 ShardSize(uint64 total, uint64 num_shards, uint64 shard_num) {
  return ShardEnd(total, num_shards, shard_num) 
    - ShardBegin(total, num_shards, shard_num);
}

// returns the least multiple of b greater than or equal to a
inline uint64 RoundUpToMultipleOf(uint64 a, uint64 b) {
  return ((a-1)/b +1) * b;
}

inline uint64 CeilingDiv(uint64 a, uint64 b) {
  return (a-1)/b + 1;
}

inline void ProbabilisticIncrementFloat(float *target, float increment, RNG *rng) {
  float min_increment = *target * 0.1;
  if (increment < min_increment) {
    if (rng->RandomFraction() < increment / min_increment) 
      increment = min_increment;
    else return;
  }
  while (1) {
    float old_val = *target;
    float new_val = old_val + increment;
    if (__sync_bool_compare_and_swap((uint32 *)target, *((uint32 *)&old_val), 
				     *((uint32*)(&new_val)))) return;
  }
}

template <class K, class V, class H>
  V OverlayHashGet(hash_map<K, V, H> * current,
		   hash_map<K, V, H> * base,
		   K key, V default_val){
  V * look = (*current) % key;
  if (!look && base) look = (*base) % key;
  if (look) return *look;
  return default_val;
}

inline string Delimit(int64 x) {
  if (x < 0) return "-" + Delimit(-x);
  string s = itoa(x);
  string ret;
  for (uint32 i=0; i<s.size(); i++) {
    if (i && ((s.size() - i) % 3 == 0)) ret += ',';
    ret += s[i];
  }
  return ret;
}

// Support for encoded numbers that are byte aligned
// high bit marked means there are more bits coming.
inline void ByteEncode(uint32 n, 
		       char *encoded, 
		       uint32 * encoded_num_bytes) {
  *encoded_num_bytes = 0;
  while (1) {
    char low_bits = n & 0x7f;
    n >>= 7;
    *encoded = low_bits | (n ? 0x80 : 0);
    encoded++;
    (*encoded_num_bytes)++;
    if (!n) return; }}

inline void ByteEncode(uint32 n, char ** p) {
  uint32 nb;
  ByteEncode(n, *p, &nb);
  *p += nb;
}

inline uint32 ByteDecode(char **p) {
  uint32 ret = 0;
  uint32 shift = 0;
  while (1) {
    char c = **p;
    ret += (c & 0x7f) << shift;
    (*p)++;
    if (!(c & 0x80)) return ret;
    shift += 7; } }

// is this the start of an encoded number.
inline bool IsStartEncodedNumber(char *p) { return !(p[-1] & 0x80); }

inline void IncrementLgAccessCount(uint8 * count, uint64 *ticker) {
  ++(*ticker);
  if (!(((1 << *count) - 1) & *ticker)) {
    __sync_fetch_and_add(count, 1); } }

// Return a position in an infinite space of 8 byte words
inline uint64 HashTrialPosition(uint64 key, uint64 trial) {
  uint64 pos_within_cache_line = (key + trial) & 0x7ull;
  uint64 which_cache_line = (key >> 3) + (trial >> 3) * (trial >> 3);
  return pos_within_cache_line + (which_cache_line << 3);
}

// Normalizing vectors to sum to 1
void Normalize(vector<double> & v);

inline int64 ExistsDiff(int64 old_num, int64 new_num) {
  return (new_num ? 1 : 0) - (old_num ? 1 : 0);
}
						 
#endif
